package 抽象数据类型.LRU缓存;

import 抽象数据类型.DoubleNode;

import java.util.HashMap;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-28
 */
public class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, DoubleNode> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最⼤容量
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        int val = map.get(key).val;
        // 利⽤ put ⽅法把该数据提前
        put(key, val);
        return val;
    }
    public DoubleNode getNode(int key) {
        DoubleNode node = map.get(key);
        return node;
    }
    public void put(int key, int val) {
        // 先把新节点 x 做出来
        DoubleNode node = getNode(key);
        if (node == null) {
            node = new DoubleNode(key, val);
        }
        if (map.containsKey(key)) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(node);
            // 更新 map 中对应的数据 245
            map.put(key, node);
        } else {
            if (cap == cache.size()) {
                // 删除链表最后⼀个数据
                DoubleNode last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(node);
            map.put(key, node);
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put(4, 4);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        lruCache.put(1, 1);
        lruCache.put(8, 1);
        lruCache.put(9, 1);
    }
}
